package com.lie.prepare.algorithm.sort;

import java.util.Arrays;

import static com.lie.prepare.algorithm.sort.InsertSort.generateData;
import static com.lie.prepare.util.Print.*;
/**
 * Created by lie on 2018/4/13.
 * 选择排序
 * 时间复杂度也是O(n^2)
 * 这种2个循环嵌套遍历的都是这样
 *
 * 为啥说选择排序不是稳定的排序
 * 首先说什么是稳定排序：
 *  5 8 5 2 9
 *  对于相同的元素，排序后，它们的相对位置，仍然是不变的（就是第一个5，经过排序结束后，仍然在第二个5前边）
 *
 *  可是选择排序的话，起手就把2和5交换了位置。（每次交换都是 第一个元素和最小的元素做交换）
 *  从而导致，第一个5现在放到了第二个5的后边。所以说选择排序是不稳定的。
 *
 *  而对于冒泡
 *  58529 55829 55289
 *  55289 52589 ..
 *  总之由于2个5相等并不触发交换
 *  所以冒泡排序是稳定的
 *
 *  稳定：
 *  https://www.cnblogs.com/codingmylife/archive/2012/10/21/2732980.html
 */
public class SelectionSort {

    public static void main(String[] args){

        int[] data = generateData();
        print("排序前 "+ Arrays.toString(data));
        directSelect(data);
        print("排序后 "+ Arrays.toString(data));

    }

    private static void directSelect(int[] data) {
        //和冒泡相似，都是两轮遍历，每次从未排序序列里找出最小的，放到已排序队列里的末尾
        for (int outI = 0; outI < data.length; outI++) {

            int lowIndex = outI;
            //对比冒泡这里亮点在于，只用来标记下标，内循环一次交换也不需要
            for (int innerI = outI +1 ; innerI < data.length; innerI++) {
                if (data[innerI]  < data[lowIndex]){
                    lowIndex = innerI;
                }
            }
            int temp = data[outI];
            data[outI] = data[lowIndex];
            data[lowIndex] = temp;

        }
    }


    private static void headSort(){
        //堆排序也是一种选择排序
        //思想是把数组变成二叉树的数据结构（所以自然有数组下标怎么映射二叉树节点的工具方法）
        //当数组的数据是一个二叉树了
        //此时再排序就是进入二叉树领域了，就有比较屌的二叉树算法来支持了
        //具体代码我完全不看不懂
        //https://blog.csdn.net/jdream314/article/details/6634863
        //时间复杂度是 n*log(n)，不稳定排序
    }
}
